﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using BLL.Relations.VectorDistances;
using DO.Clustering;

namespace BLL.Clustering
{
    public class HierarchyClusterManager
    {
        public static Dictionary<int,List<int>> BuildClusters(
            Dictionary<int,Dictionary<int,double>> entityDistances,
            Dictionary<int,Dictionary<int,FeatureFreq>> docFeatFreqs,
            Dictionary<int,double> termWeights)
        {
            List<int> remainingDocIDs = new List<int>();
            List<int> rootClusterIDs = new List<int>();
            remainingDocIDs.AddRange(entityDistances.Keys);
            Dictionary<int, List<int>> clusterTerms = new Dictionary<int, List<int>>();
            Dictionary<int, Cluster> clusterResult = new Dictionary<int, Cluster>();
            Dictionary<int, Dictionary<int, double>> clusterDocDistances = new Dictionary<int, Dictionary<int, double>>();
            Dictionary<int, Dictionary<int, double>> clusterClusterDistances = new Dictionary<int, Dictionary<int, double>>();

            // iteration 
            int iterationCount = 0;
            WeightedFeatureSimilarityCalculator calc=new WeightedFeatureSimilarityCalculator();
            while (remainingDocIDs.Count > 0 || rootClusterIDs.Count > 1)
            {
                Grow(calc, remainingDocIDs, 
                    entityDistances, docFeatFreqs, termWeights,
                    clusterDocDistances, clusterClusterDistances,
                    rootClusterIDs, clusterTerms, clusterResult);
                iterationCount++;
                if(iterationCount >100)
                    break;
            }

            foreach(int orphanDocID in remainingDocIDs)
            {
                int newClusterID = NextClusterID(clusterResult);
                Cluster orphanCluster=new Cluster();
                orphanCluster.ChildClusterIDs=new List<int>();
                orphanCluster.ClusterID = newClusterID;
                orphanCluster.Distance = 0;
                orphanCluster.DocIDs=new List<int>();
                orphanCluster.DocIDs.Add(orphanDocID);
                orphanCluster.SupportiveTermWeights=new Dictionary<int, double>();
                clusterResult.Add(newClusterID, orphanCluster);
            }

            Dictionary<int,List<int>> clusteredDocs=new Dictionary<int, List<int>>();
            foreach(int clusterID in clusterResult.Keys)
            {
                clusteredDocs.Add(clusterID, clusterResult[clusterID].DocIDs);
            }
            return clusteredDocs;
        }

        #region grow
        private static void Grow(WeightedFeatureSimilarityCalculator calc,
            List<int> remainingDocIDs,
            Dictionary<int, Dictionary<int, double>> entityDistances,
            Dictionary<int,Dictionary<int,FeatureFreq>> docFeatFreqs,
            Dictionary<int, double> termWeights,
            Dictionary<int, Dictionary<int, double>> clusterDocDistances,
            Dictionary<int, Dictionary<int, double>> clusterClusterDistances,
            List<int> rootClusterIDs,
            Dictionary<int, List<int>> clusterTerms,
            Dictionary<int, Cluster> clusterResult)
        {
            double distance = double.PositiveInfinity;
            int itemID1 = 0;
            int itemID2 = 0;
            bool item1IsCluster = false;
            bool item2IsCluster = false;
            // doc-doc
            foreach (int docID1 in remainingDocIDs)
            {
                foreach (int docID2 in remainingDocIDs)
                {
                    if (docID1 != docID2)
                    {
                        double docdocDistance = 1;
                        if (entityDistances.ContainsKey(docID1) && entityDistances[docID1].ContainsKey(docID2))
                        {
                            docdocDistance = entityDistances[docID1][docID2];
                        }
                        if (entityDistances.ContainsKey(docID2) && entityDistances[docID2].ContainsKey(docID1))
                        {
                            docdocDistance = entityDistances[docID2][docID1];
                        }
                        if (docdocDistance < distance)
                        {
                            distance = docdocDistance;
                            itemID1 = docID1;
                            itemID2 = docID2;
                            item1IsCluster = false;
                            item2IsCluster = false;
                        }
                    }
                }
            }
            // doc-cluster 
            foreach (int docID in remainingDocIDs)
            {
                foreach (int clusterID in rootClusterIDs)
                {
                    if (clusterDocDistances.ContainsKey(clusterID) &&
                        clusterDocDistances[clusterID].ContainsKey(docID))
                    {
                        double clusterDocDistance =
                            clusterDocDistances[clusterID][docID];
                        if (clusterDocDistance < distance)
                        {
                            distance = clusterDocDistance;
                            itemID1 = docID;
                            item1IsCluster = false;
                            itemID2 = clusterID;
                            item2IsCluster = true;
                        }
                    }
                }
            }
            // cluster-cluster 
            foreach (int clusterID1 in rootClusterIDs)
            {
                foreach (int clusterID2 in rootClusterIDs)
                {
                    if (clusterID1 != clusterID2)
                    {
                        if (clusterClusterDistances.ContainsKey(clusterID1) &&
                            clusterClusterDistances[clusterID1].ContainsKey(clusterID2))
                        {
                            double clusterClusterDistance =
                                clusterClusterDistances[clusterID1][clusterID2];
                            if (clusterClusterDistance < distance)
                            {
                                distance = clusterClusterDistance;
                                itemID1 = clusterID1;
                                item1IsCluster = true;
                                itemID2 = clusterID2;
                                item2IsCluster = true;
                            }
                        }
                        else if (clusterClusterDistances.ContainsKey(clusterID2) &&
                            clusterClusterDistances[clusterID2].ContainsKey(clusterID1))
                        {
                            double clusterClusterDistance =
                                clusterClusterDistances[clusterID2][clusterID1];
                            if (clusterClusterDistance < distance)
                            {
                                distance = clusterClusterDistance;
                                itemID1 = clusterID1;
                                item1IsCluster = true;
                                itemID2 = clusterID2;
                                item2IsCluster = true;
                            }
                        }
                    }
                }
            }
            if (distance < double.PositiveInfinity && itemID1 > 0 && itemID2 > 0)
            {
                if (item1IsCluster && item2IsCluster)
                {
                    MergeClusterPair(calc, itemID1, itemID2,
                         distance, docFeatFreqs, termWeights, 
                         clusterDocDistances, clusterClusterDistances,
                         remainingDocIDs,
                        rootClusterIDs, clusterResult, clusterTerms);
                }
                else if (!item1IsCluster && !item2IsCluster)
                {
                    MergeDocPair(calc, itemID1, itemID2, distance, docFeatFreqs, termWeights,
                        clusterDocDistances, clusterClusterDistances,
                        remainingDocIDs, clusterTerms, clusterResult, rootClusterIDs);
                }
                else if (item1IsCluster && !item2IsCluster)
                {
                    MergeDocAndCluster(calc, itemID2, itemID1, distance, 
                        docFeatFreqs, termWeights, clusterDocDistances,
                        clusterClusterDistances, 
                        remainingDocIDs, clusterTerms, 
                        clusterResult, rootClusterIDs);
                }
                else
                {
                    MergeDocAndCluster(calc, itemID1, itemID2, distance,
                        docFeatFreqs, termWeights, clusterDocDistances,
                        clusterClusterDistances, 
                        remainingDocIDs, clusterTerms,
                        clusterResult, rootClusterIDs);
                }
            }
        }

        private static void MergeDocPair(
            WeightedFeatureSimilarityCalculator calc, 
            int docID1, int docID2, double distance,
            Dictionary<int, Dictionary<int, FeatureFreq>> docFeatFreqs,
            Dictionary<int,double> termWeights,
            Dictionary<int, Dictionary<int, double>> clusterDocDistances,
            Dictionary<int, Dictionary<int, double>> clusterClusterDistances,
            List<int> remainingDocIDs,
            Dictionary<int, List<int>> clusterTerms,
            Dictionary<int, Cluster> clusterResult,
            List<int> rootClusterIDs)
        {
            remainingDocIDs.Remove(docID1);
            remainingDocIDs.Remove(docID2);

            int clusterID = NextClusterID(clusterResult);
            List<int> unionTermIDs = new List<int>();
            Dictionary<int, FeatureFreq> termFreqs1 = docFeatFreqs[docID1];
            int[] termIDs1 = new int[termFreqs1.Count];
            termFreqs1.Keys.CopyTo(termIDs1, 0);
            unionTermIDs.AddRange(termIDs1);
            Dictionary<int, FeatureFreq> termFreqs2 = docFeatFreqs[docID2];
            foreach (int termID2 in termFreqs2.Keys)
            {
                if (!unionTermIDs.Contains(termID2))
                {
                    unionTermIDs.Add(termID2);
                }
            }
            clusterTerms.Add(clusterID, unionTermIDs);
            distance = distance / 2;
            Cluster cluster = new Cluster();
            cluster.ClusterID = clusterID;
            cluster.DocIDs = new List<int>();
            cluster.DocIDs.Add(docID1);
            cluster.DocIDs.Add(docID2);
            cluster.Distance = distance;
            cluster.SupportiveTermWeights = new Dictionary<int, double>();
            foreach (int termID in unionTermIDs)
            {
                if (termFreqs1.ContainsKey(termID) && termFreqs2.ContainsKey(termID))
                {
                    double weight = termFreqs1[termID].Weight * termFreqs1[termID].Count +
                                    termFreqs2[termID].Count * termFreqs2[termID].Weight;
                    cluster.SupportiveTermWeights.Add(termID, weight);
                }
            }
            //cluster.LeftChildID = docID1;
            //cluster.LeftChildIsCluster = false;
            //cluster.RightChildID = docID2;
            //cluster.RightChildIsCluster = false;
            clusterResult.Add(clusterID, cluster);
            DistanceManager.UpdateClusterDistances(calc, clusterID,
                docFeatFreqs, termWeights, clusterDocDistances,
                clusterClusterDistances,
                clusterResult, remainingDocIDs, clusterTerms);
            if (!rootClusterIDs.Contains(clusterID))
                rootClusterIDs.Add(clusterID);
        }

        private static void MergeClusterPair(
            WeightedFeatureSimilarityCalculator calc,
            int clusterID1, int clusterID2, double distance,
            Dictionary<int, Dictionary<int, FeatureFreq>> docFeatFreqs,
            Dictionary<int, double> termWeights,
            Dictionary<int, Dictionary<int, double>> clusterDocDistances,
            Dictionary<int, Dictionary<int, double>> clusterClusterDistances,
            List<int> remainingDocIDs,
            List<int> rootClusterIDs,
            Dictionary<int, Cluster> clusterResult,
            Dictionary<int, List<int>> clusterTerms)
        {
            int clusterID = NextClusterID(clusterResult);
            List<int> unionTermIDs = new List<int>();
            List<int> termIDs1 = clusterTerms[clusterID1];
            unionTermIDs.AddRange(termIDs1.ToArray());
            List<int> termIDs2 = clusterTerms[clusterID2];
            foreach (int termID2 in termIDs2)
            {
                if (!unionTermIDs.Contains(termID2))
                {
                    unionTermIDs.Add(termID2);
                }
            }
            clusterTerms.Add(clusterID, unionTermIDs);
            distance = distance / 2;
            Cluster cluster = new Cluster();
            cluster.ClusterID = clusterID;
            cluster.DocIDs = new List<int>();
            cluster.ChildClusterIDs = new List<int>();
            cluster.ChildClusterIDs.Add(clusterID1);
            cluster.ChildClusterIDs.Add(clusterID2);
            cluster.Distance = distance;
            cluster.SupportiveTermWeights = new Dictionary<int, double>();
            foreach (int termID in unionTermIDs)
            {
                if (termIDs1.Contains(termID) && termIDs2.Contains(termID))
                {
                    cluster.SupportiveTermWeights.Add(termID, 2);
                }
            }
            //cluster.LeftChildID = clusterID1;
            //cluster.LeftChildIsCluster = true;
            //cluster.RightChildID = clusterID2;
            //cluster.RightChildIsCluster = true;
            clusterResult.Add(clusterID, cluster);
            DistanceManager.UpdateClusterDistances(calc, clusterID,
                docFeatFreqs, termWeights, clusterDocDistances, clusterClusterDistances,
                clusterResult, remainingDocIDs, clusterTerms);

            rootClusterIDs.Remove(clusterID1);
            rootClusterIDs.Remove(clusterID2);
            rootClusterIDs.Add(clusterID);
        }

        private static void MergeDocAndCluster(
            WeightedFeatureSimilarityCalculator calc,
            int docID, int childClusterID, double distance, 
            Dictionary<int, Dictionary<int, FeatureFreq>> docFeatFreqs,
            Dictionary<int, double> termWeights,
            Dictionary<int, Dictionary<int, double>> clusterDocDistances,
            Dictionary<int, Dictionary<int, double>> clusterClusterDistances,
            List<int> remainingDocIDs,
            Dictionary<int, List<int>> clusterTerms,
            Dictionary<int, Cluster> clusterResult,
            List<int> rootClusterIDs)
        {
            remainingDocIDs.Remove(docID);
            int newClusterID = NextClusterID(clusterResult);
            List<int> unionTermIDs = new List<int>();
            Dictionary<int, FeatureFreq> termFreqs1 = docFeatFreqs[docID];
            int[] termIDs1 = new int[termFreqs1.Count];
            termFreqs1.Keys.CopyTo(termIDs1, 0);
            unionTermIDs.AddRange(termIDs1);
            List<int> termIDs2 = clusterTerms[childClusterID];
            foreach (int termID2 in termIDs2)
            {
                if (!unionTermIDs.Contains(termID2))
                {
                    unionTermIDs.Add(termID2);
                }
            }
            clusterTerms.Add(newClusterID, unionTermIDs);
            distance = distance / 2;
            Cluster cluster = new Cluster();
            cluster.ClusterID = newClusterID;
            cluster.DocIDs = new List<int>();
            cluster.DocIDs.Add(docID);
            cluster.ChildClusterIDs = new List<int>();
            cluster.ChildClusterIDs.Add(childClusterID);
            cluster.Distance = distance;
            cluster.SupportiveTermWeights = new Dictionary<int, double>();
            foreach (int termID in unionTermIDs)
            {
                if (termFreqs1.ContainsKey(termID) && termIDs2.Contains(termID))
                {
                    double weight = termFreqs1[termID].Count * termFreqs1[termID].Weight + 1;
                    cluster.SupportiveTermWeights.Add(termID, weight);
                }
            }
            //cluster.LeftChildID = childClusterID;
            //cluster.LeftChildIsCluster = true;
            //cluster.RightChildID = docID;
            //cluster.RightChildIsCluster = false;
            clusterResult.Add(newClusterID, cluster);
            DistanceManager.UpdateClusterDistances(calc, newClusterID,
                docFeatFreqs, termWeights, 
                clusterDocDistances, clusterClusterDistances,
                clusterResult, remainingDocIDs, clusterTerms);

            rootClusterIDs.Remove(childClusterID);
            rootClusterIDs.Add(newClusterID);
        }

        private static int NextClusterID(Dictionary<int, Cluster> clusterResult)
        {
            int lastClusterID = 0;
            if (clusterResult.Count > 0)
            {
                foreach (int clusterID in clusterResult.Keys)
                {
                    if (clusterID > lastClusterID)
                        lastClusterID = clusterID;
                }
            }
            return lastClusterID + 1;
        }
        #endregion
    }
}
